package com.z.test;

import java.util.Arrays;

public class InsertionSort {
    private static int[] arr = new int[]{1,4,3,5,6,2};

    // 插入排序
    public static void insertion_sort(int[] arrs){
        int[] arr = Arrays.copyOf(arrs,arrs.length);
        int len = arr.length;
        System.out.println("插入排序 insertion sort:");
        printArrs("原始：", arr);
        int minIndex, // 对比的开始下标，已排序的最后一个
                current; // 未排序的第一个元素
        for(int i = 1; i < len ; i++){
            minIndex = i - 1 ;
            current = arr[i];
            System.out.println("第" + (i) + "轮 " + minIndex);
            printArrs("之前：" , arr);
            while(minIndex > 0 && arr[minIndex] > current){
                System.out.println("比较：arr[" + minIndex + "]和current " + arr[minIndex] + "和" + current);
                arr[minIndex + 1] = arr[minIndex];
                minIndex--;
            }
            arr[minIndex + 1] = current;
            printArrs("之后：" , arr);
        }
        printArrs("最终：" , arr);
    }
    public static void main(String[] args) {
        insertion_sort(arr);
    }







    static void printArrs(String preStr , int[] arr){
        String str = "";
        for(int i=0;i<arr.length;i++){
            str += arr[i] + ",";
        }
        System.out.println(preStr + str.substring(0,str.length()-1));
    }
}
